package com.hanxiaozhang.no10leetcode.array;

import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈杨辉三角〉
 * <p>
 * 给一个行数n，输出n行杨辉三角
 *
 * @author hanxinghua
 * @create 2024/1/23
 * @since 1.0.0
 */
public class No118PascalTriangle {


    public static void main(String[] args) {
        System.out.println(method1(5));
        System.out.println(method2(5));

    }


    /**
     * 自己想的方法
     *
     * @param n
     * @return
     */
    private static List<List<Integer>> method1(int n) {
        List<List<Integer>> result = new ArrayList();
        if (n < 1) {
            return result;
        }

        for (int i = 0; i < n; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(1);
            if (i == 0) {
                result.add(list);
            } else if (i == 1) {
                list.add(1);
                result.add(list);
            } else {
                // 从1位置开始处理，条件表达式：j < i
                for (int j = 1; j < i; j++) {
                    list.add(result.get(i - 1).get(j - 1) + result.get(i - 1).get(j));
                }
                list.add(1);
                result.add(list);
            }
        }
        return result;
    }


    /**
     * 其他高人的方法
     *
     * @param numRows
     * @return
     */
    public static List<List<Integer>> method2(int numRows) {
        // 结果集
        List<List<Integer>> res = new ArrayList<>();
        // 当前行
        int row = 0;
        while (row < numRows) {
            // 当前行的结果
            List<Integer> curr = new ArrayList<>();
            int index = 0;
            // 处理当前行每一个元素
            // 特殊点：第0行，不进入该循环；第1行，进入循环，只处理index == 0就结束循环
            while (index < row) {
                // 第0个位置
                if (index == 0) {
                    curr.add(1);
                    index++;
                    continue;
                }
                // 非第0个位置 = 上一行的index - 1 + 上一行的index
                curr.add(res.get(row - 1).get(index - 1) + res.get(row - 1).get(index));
                index++;
            }
            curr.add(1);
            res.add(curr);
            row++;
        }
        return res;
    }

}
